AI ninja project [day 10] 基因演算法

2021 iThome 鐵人賽

DAY 10

AI & Data

AI ninja project系列第 10 篇

13th鐵人賽

wilsonsujames

2021-09-10 10:54:28

3391 瀏覽

分享至

這一篇介紹，將使用DEAP這個套件，
其實，現在比較紅及使用上比較簡便的套件應該是PyGAD，
但是，由於目前PyGAD還無法以比較簡單的方法解決旅行推銷員問題(需要自己改寫突變、配對等等的機制，)。
所以下面採用DEAP來說明，這裡附上兩個套件的官方文件:

https://pygad.readthedocs.io/en/latest/

https://deap.readthedocs.io/en/master/index.html

這裡要解決的問題是旅行推銷員問題，
假設要經過所有城市，並且最終要回到起始城市，計算出最短的路徑。

安裝:

pip install deap

我使用官網的範例:
https://github.com/DEAP/deap/blob/master/examples/ga/tsp.py

gr17.json

{
    "TourSize" : 17,
    "OptTour" : [15, 11, 8, 4, 1, 9, 10, 2, 14, 13, 16, 5, 7, 6, 12, 3, 0],
    "OptDistance" : 2085,
    "DistanceMatrix" :
        [[0, 633, 257, 91, 412, 150, 80, 134, 259, 505, 353, 324, 70, 211, 268, 246, 121],
        [633, 0, 390, 661, 227, 488, 572, 530, 555, 289, 282, 638, 567, 466, 420, 745, 518],
        [257, 390, 0, 228, 169, 112, 196, 154, 372, 262, 110, 437, 191, 74, 53, 472, 142],
        [91, 661, 228, 0, 383, 120, 77, 105, 175, 476, 324, 240, 27, 182, 239, 237, 84],
        [412, 227, 169, 383, 0, 267, 351, 309, 338, 196, 61, 421, 346, 243, 199, 528, 297],
        [150, 488, 112, 120, 267, 0, 63, 34, 264, 360, 208, 329, 83, 105, 123, 364, 35],
        [80, 572, 196, 77, 351, 63, 0, 29, 232, 444, 292, 297, 47, 150, 207, 332, 29],
        [134, 530, 154, 105, 309, 34, 29, 0, 249, 402, 250, 314, 68, 108, 165, 349, 36],
        [259, 555, 372, 175, 338, 264, 232, 249, 0, 495, 352, 95, 189, 326, 383, 202, 236],
        [505, 289, 262, 476, 196, 360, 444, 402, 495, 0, 154, 578, 439, 336, 240, 685, 390],
        [353, 282, 110, 324, 61, 208, 292, 250, 352, 154, 0, 435, 287, 184, 140, 542, 238],
        [324, 638, 437, 240, 421, 329, 297, 314, 95, 578, 435, 0, 254, 391, 448, 157, 301],
        [70, 567, 191, 27, 346, 83, 47, 68, 189, 439, 287, 254, 0, 145, 202, 289, 55],
        [211, 466, 74, 182, 243, 105, 150, 108, 326, 336, 184, 391, 145, 0, 57, 426, 96],
        [268, 420, 53, 239, 199, 123, 207, 165, 383, 240, 140, 448, 202, 57, 0, 483, 153],
        [246, 745, 472, 237, 528, 364, 332, 349, 202, 685, 542, 157, 289, 426, 483, 0, 336],
        [121, 518, 142, 84, 297, 35, 29, 36, 236, 390, 238, 301, 55, 96, 153, 336, 0]]
    }

可以發現有17座城市，DistanceMatrix每一個元素的array為第幾個城市到其他城市的距離。

tsp.py

import array
import random
import json
import matplotlib.pyplot as plt
import numpy

from deap import algorithms
from deap import base
from deap import creator
from deap import tools

with open("gr17.json", "r") as tsp_data:
    tsp = json.load(tsp_data)

distance_map = tsp["DistanceMatrix"]
IND_SIZE = tsp["TourSize"]

引入模組，查看剛才json中的距離矩陣及城市數量。

creator.create("FitnessMin", base.Fitness, weights=(-1.0,))
creator.create("Individual", array.array, typecode='i', fitness=creator.FitnessMin)

須找的解答是最小值，weights的參數放-1(尋找最大值FitnessMax)。
再來創建每一個染色體個體為一個array，typecode的對照可以由array模組來查看，
https://docs.python.org/zh-tw/3.8/library/array.html

toolbox = base.Toolbox()

建立工具箱，演算法的流程使用這個工具箱來建立註冊與操作。

toolbox.register("indices", random.sample, range(IND_SIZE), IND_SIZE)

# Structure initializers
toolbox.register("individual", tools.initIterate, creator.Individual, toolbox.indices)
toolbox.register("population", tools.initRepeat, list, toolbox.individual)

這裡要建立染色體池，將每一條染色體以亂數生成
([0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16]可能的染色體範例)，
放入染色體池。

def evalTSP(individual):
    distance = distance_map[individual[-1]][individual[0]]
    for gene1, gene2 in zip(individual[0:-1], individual[1:]):
        distance += distance_map[gene1][gene2]
    return distance,

這個function就是我們要解決的問題，每條染色體代表一個路徑行走城市的順序，
那回傳該路徑所要行走的距離。(值得注意的是評估函數回傳的格式為Tuple，所以有那個逗點的存在)

toolbox.register("mate", tools.cxPartialyMatched)
toolbox.register("mutate", tools.mutShuffleIndexes, indpb=0.05)
toolbox.register("select", tools.selTournament, tournsize=3)
toolbox.register("evaluate", evalTSP)

最後一項評估evaluate 的流程，採用了我們上面的function evalTSP來評估路徑的距離，
配對採用套件預設的流程，mate的流程為染色體與染色體之間交換基因，
突變為該染色體基因上變異，選擇從染色體池中去掉一些回傳距離太長的染色體。

def main():

    pop = toolbox.population(n=300)

    hof = tools.HallOfFame(1)
    stats = tools.Statistics(lambda ind: ind.fitness.values)
    stats.register("avg", numpy.mean)
    stats.register("std", numpy.std)
    stats.register("min", numpy.min)
    stats.register("max", numpy.max)
    
    algorithms.eaSimple(pop, toolbox, 0.7, 0.2, 40, stats=stats, 
                        halloffame=hof)
    best = hof.items[0]
    print('Best Individual = ', best)                    

    return pop, stats, hof

if __name__ == "__main__":
    main()